package com.future;

/**
 * Description:
 * 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
 * <p>
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/2/28:21:56
 */
public class Solution_longestIncreasingPath_329 {

    public static void main(String[] args) {


        int[][] matrix = new int[][]{
                {9, 9, 4}, {6, 6, 8}, {2, 1, 1}
        };
        System.out.println(longestIncreasingPath_1(matrix));
    }

    /**
     * 加缓存，通过
     *
     * @param matrix
     * @return
     */
    public static int longestIncreasingPath(int[][] matrix) {
        if (matrix == null) {
            return 0;
        }
        int ans = 0;
        int N = matrix.length; // 行
        int M = matrix[0].length;// 列
        int[][] dp = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                ans = Math.max(ans, process(matrix, i, j, dp));
            }
        }
        return ans;

    }


    private static int process(int[][] matrix, int i, int j, int[][] dp) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int up = i < matrix.length - 1 && matrix[i][j] < matrix[i + 1][j] ? process(matrix, i + 1, j, dp) : 0;
        int down = i > 0 && matrix[i][j] < matrix[i - 1][j] ? process(matrix, i - 1, j, dp) : 0;
        int left = j > 0 && matrix[i][j] < matrix[i][j - 1] ? process(matrix, i, j - 1, dp) : 0;
        int right = j < matrix[0].length - 1 && matrix[i][j] < matrix[i][j + 1] ? process(matrix, i, j + 1, dp) : 0;
        dp[i][j] = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
        return dp[i][j];
    }


    /**
     * 暴力方法：超时
     *
     * @param matrix
     * @return
     */
    public static int longestIncreasingPath_1(int[][] matrix) {
        if (matrix == null) {
            return 0;
        }
        int ans = 0;
        int N = matrix.length; // 行
        int M = matrix[0].length;// 列
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                ans = Math.max(ans, process_1(matrix, i, j));
            }
        }
        return ans;
    }

    private static int process_1(int[][] matrix, int i, int j) {

        int up = i < matrix.length - 1 && matrix[i][j] < matrix[i + 1][j] ? process_1(matrix, i + 1, j) : 0;
        int down = i > 0 && matrix[i][j] < matrix[i - 1][j] ? process_1(matrix, i - 1, j) : 0;
        int left = j > 0 && matrix[i][j] < matrix[i][j - 1] ? process_1(matrix, i, j - 1) : 0;
        int right = j < matrix[0].length - 1 && matrix[i][j] < matrix[i][j + 1] ? process_1(matrix, i, j + 1) : 0;

        return Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    }

}
